/*public class test {
}*/
public class QuickSelect {
    // 同快速排序的分区操作
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left - 1;

        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = temp;

        return i + 1;
    }

    // 查找arr中第k小的元素（k从0开始，如k=0是最小元素）
    private static int select(int[] arr, int left, int right, int k) {
        if (left == right) return arr[left]; // 基线条件：只有一个元素

        int pivotIndex = partition(arr, left, right); // 基准值索引
        if (pivotIndex == k) {
            return arr[pivotIndex]; // 基准值就是第k小元素，直接返回
        } else if (pivotIndex > k) {
            return select(arr, left, pivotIndex - 1, k); // 左半区查找
        } else {
            return select(arr, pivotIndex + 1, right, k); // 右半区查找
        }
    }

    // 测试（查找第3小元素，数组[8,4,5,7,1,3,6,2]的第3小是4）
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int k = 3; // 第3小（0-based）
        System.out.println("第" + (k + 1) + "小的元素：" + select(arr, 0, arr.length - 1, k)); // 输出：4
    }
}